package com.code.test.second.link;

/**
 * 面试题 02.07. 链表相交
 * 同：160.链表相交
 * <p>
 * 力扣题目链接
 * <p>
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 */
public class SCode207 {
    public static void main(String[] args) {
        SNode headA21 = new SNode(21);
        SNode headA22 = new SNode(22);
        SNode headA23 = new SNode(23);
        SNode n4 = new SNode(24);
        SNode n5 = new SNode(99);
        SNode n6 = new SNode(98);
        SNode n7 = new SNode(100);

        headA21.setNext(headA22);
        headA22.setNext(headA23);
        headA23.setNext(n4);


        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        /**
         * ========================================
         */

        SNode headB11 = new SNode(11);
        SNode headB12 = new SNode(12);
        SNode headB13 = new SNode(13);
        SNode headB14 = new SNode(14);

        headB11.setNext(headB12);
        headB12.setNext(headB13);
        headB13.setNext(headB14);
        headB14.setNext(n4);

        SNode tempHeadA = headA21;
        SNode tempHeadB = headB11;
        while (headA21 != null) {
            System.out.print(headA21.getVal() + "→");
            headA21 = headA21.getNext();
        }

        System.out.println("");
        while (headB11 != null) {
            System.out.print(headB11.getVal() + "→");
            headB11 = headB11.getNext();
        }

        System.out.println("");

        SNode node = findSampleNode2(tempHeadA, tempHeadB);

        while (node != null) {
            System.out.print(node.val + "→");
            node = node.next;
        }
        System.out.println("");

    }

    /**
     * 合并链表实现同时移动
     * pA走过的路径为A链+B链
     * pB走过的路径为B链+A链
     * <p>
     * 原因： pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
     */
    public static SNode findSampleNode(SNode nodeA, SNode nodeB) {
        SNode p1 = nodeA;
        SNode p2 = nodeB;

        /**
         *  原理是，
         *  p1 = nodeA + nodeB:[1,2,3,4,5,6,7] [8,9,5,6,7] → [1,2,3,4,5,6,7,8,9,5,6,7]
         *  p2 = nodeB + nodeA:[8,9,5,6,7] [1,2,3,4,5,6,7]  → [8,9,5,6,7,1,2,3,4,5,6,7]
         *  每次都走了相同的节点，现在因为p1、p2是长度相同的，如果在遇到相同节点时即相交，没有即到末尾
         */
        while (p1 != p2) {
            //p1 走一步，如果走到A链表的末尾，转到链表B
            p1 = p1 != null ? nodeA.next : nodeB;
            //p2 走一步，如果走到B链表的末尾，转到链表A
            p2 = p2 != null ? nodeB.next : nodeA;
        }
        return p1;
    }

    public static SNode findSampleNode2(SNode nodeA, SNode nodeB) {
        SNode p1 = nodeA;
        SNode p2 = nodeB;
        while (p1 != p2) {
            //这里是
            p1 = p1 != null ? p1.next : nodeB;
            p2 = p2 != null ? p2.next : nodeA;
        }
        return p1;
    }
}
